package org.ayachinene.leetcode.problems;

import java.util.Arrays;

public class P07 {

    private static final int SRC = 0;
    private static final int TAR = 1;
    /**
     * @param n:最终到达小朋友的编号
     * @param relation
     * @param k：剩余步数
     * @return
     */
    public int numWays(int n, int[][] relation, int k) {

        if(k == 1)
            for (int[] rel : relation) {
                    if (rel[SRC] == 0 && rel[TAR] == n - 1)
                        return 1;
            }

        if(k <= 0)
            return 0;

        int sumWay = 0;
        for (int[] rel : relation) {
            if (rel[TAR] == n - 1){
                sumWay += numWays(rel[SRC] + 1, relation, k - 1);
            }
        }
        return sumWay;
    }
}
